package newcoder_exp.comprehensive;

import java.util.*;

import org.junit.Test;

import tree.*;

public class Comp1 {

    // 1. 字节跳动部分
    class ByteDance {
        // 2. 之字形打印二叉树
        /*
         * 利用双向队列记录二叉树层序遍历的元素 每次打印一层 利用全局的bool变量说明这次是正序还是逆序
         * 
         * 這裡使用新隊列來保證輸入隊列的順序，必然仔細想很麻煩
         * 注意：逆序时保证先加右子树。
         */
        public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
            if (root == null)
                return new ArrayList<>();
            Deque<TreeNode> deque = new LinkedList<>();
            deque.offerLast(root);
            TreeNode cur;
            boolean reverse = false;
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            int size;

            while (!deque.isEmpty()) {
                size = deque.size();
                ArrayList<Integer> list = new ArrayList<>();
                Deque<TreeNode> newDeque = new LinkedList<>();
                for (int i = 0; i < size; i++) {
                    if (reverse) {
                        cur = deque.pollLast();
                        list.add(cur.val);
                        if (cur.right != null) {
                            newDeque.offerLast(cur.right);
                        }
                        if (cur.left != null) {
                            newDeque.offerLast(cur.left);
                        }

                    } else {
                        cur = deque.pollLast();
                        list.add(cur.val);
                        if (cur.left != null) {
                            newDeque.offerLast(cur.left);
                        }
                        if (cur.right != null) {
                            newDeque.offerLast(cur.right);
                        }
                    }

                }
                res.add(list);
                reverse = !reverse;
                deque = newDeque;
            }
            return res;
        }
    }

    @Test
    public void by1() {
        ByteDance bd = new ByteDance();
        TreeNode root = TreeUtils.createTree(new Integer[] { 3, 9, 20, 15, 7, 1, 2 ,4,5,6,7});
        ArrayList res = bd.zigzagLevelOrder(root);
        System.out.println(res);
    }
}
